﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Brainee.Search;

namespace Brainee.Examples.Search
{
  /// <summary>
  /// The goal of the 8-queens problem is to place eight queens on a chessboard such that
  /// no queen attacks any other. A queen attacks any piece in the same row, column or 
  /// diagonal.
  /// 
  ///     +---+---+---+---+---+---+---+---+
  ///     | X |   |   |   |   |   |   |   |
  ///     +---+---+---+---+---+---+---+---+
  ///     |   |   |   |   |   |   | X |   |
  ///     +---+---+---+---+---+---+---+---+
  ///     |   |   |   |   | X |   |   |   |
  ///     +---+---+---+---+---+---+---+---+
  ///     |   |   |   |   |   |   |   | X |
  ///     +---+---+---+---+---+---+---+---+
  ///     |   | X |   |   |   |   |   |   |
  ///     +---+---+---+---+---+---+---+---+
  ///     |   |   |   | X |   |   |   |   |
  ///     +---+---+---+---+---+---+---+---+
  ///     |   |   |   |   |   | X |   |   |
  ///     +---+---+---+---+---+---+---+---+
  ///     |   |   | X |   |   |   |   |   |
  ///     +---+---+---+---+---+---+---+---+
  /// 
  /// There are two main kinds of formulation. An incremental formulation involves operators that 
  /// augment the state description, starting with an empty state; for the 8-queens problem, this 
  /// means that each action adds a queen to the state. A complete-state formulation starts with
  /// all 8 queens on the board and moves them around. In either case, the path cost is of no 
  /// interest because only the final state counts.
  ///   - States: Any arrangement of 0 to 8 queens on the board is a state.
  ///   - Initial state: No queens on the board.
  ///   - Successor function: Add a queen to any empty square.
  ///   - Goal test: 8 queens are on the board, none attacked.
  /// A better formulation would prohibit placing a queen in any square that is already attacked:
  ///   - States: Arrangements of n queens (0 &lte; n &lte; 8), one per column in the leftmost n
  ///     columns, with no queen attacking another are states.
  ///   - Successor function: Add a queen to any square in the leftmost empty column such that it
  ///     is not attacked by any other queen.
  /// </summary>
  public class EightQueens : IProblem
  {
#region States

    public class State : IState
    {
      public int [,] Board { get; private set; }
      public int Column { get; private set; }

      public State ()
      {
        Board = new int [8, 8];
        Column = 0;
      }

      public State (State state, int row)
      {
        Board = (int [,])state.Board.Clone ();
        for (int y = 0; y < 8; y++)
        {
          Board [state.Column, y] = -1;
        }
        for (int x = state.Column + 1; x < 8; x++)
        {
          int offset = x - state.Column;

          Board [x, row] = -1;

          if (row - offset >= 0)
            Board [x, row - offset] = -1;

          if (row + offset < 8)
            Board [x, row + offset] = -1;
        }
        Board [state.Column, row] = 1;
        Column = state.Column + 1;
      }

      //public static State Random
      //{
      //  get
      //  {
      //    Random random = new Random ((int)DateTime.Now.Ticks);
      //    return new State ((Status)random.Next (2), (Status)random.Next (2), (Location)random.Next (2));
      //  }
      //}
    }

    private class StateEqualityComparer : IEqualityComparer<IState>
    {
      public bool Equals (IState x, IState y)
      {
        for (int i = 0; i < 8; i++)
          for (int j = 0; j < 8; j++)
            if (((State)x).Board [i, j] != ((State)y).Board [i, j])
              return false;
        return true;
      }

      public int GetHashCode (IState obj)
      {
        int hash = 0;
        for (int i = 0; i < 8; i++)
          for (int j = 0; j < 8; j++)
            hash ^= ((State)obj).Board [i, j];
        return hash;
      }
    }

#endregion
#region Actions

    public class Actions : IAction
    {
      public class Row0Action : Actions { }
      public static readonly Row0Action Row0 = new Row0Action ();
      public class Row1Action : Actions { }
      public static readonly Row1Action Row1 = new Row1Action ();
      public class Row2Action : Actions { }
      public static readonly Row2Action Row2 = new Row2Action ();
      public class Row3Action : Actions { }
      public static readonly Row3Action Row3 = new Row3Action ();
      public class Row4Action : Actions { }
      public static readonly Row4Action Row4 = new Row4Action ();
      public class Row5Action : Actions { }
      public static readonly Row5Action Row5 = new Row5Action ();
      public class Row6Action : Actions { }
      public static readonly Row6Action Row6 = new Row6Action ();
      public class Row7Action : Actions { }
      public static readonly Row7Action Row7 = new Row7Action ();
    }

#endregion
#region Constructor

    public EightQueens ()
    {
      InitialState = new State ();
    }

#endregion
#region IProblem implementation

    public IState InitialState
    {
      get;
      set;
    }

    public IEqualityComparer<IState> StateComparer
    {
      get { return new StateEqualityComparer (); }
    }

    public IEnumerable<ActionState> Successors (IState state)
    {
      State s = state as State;
      if (s == null)
        throw new ArgumentException ();

      List<ActionState> successors = new List<ActionState> ();

      if (s.Board [s.Column, 0] == 0)
        successors.Add (new ActionState (Actions.Row0, new State (s, 0)));
      if (s.Board [s.Column, 1] == 0)
        successors.Add (new ActionState (Actions.Row1, new State (s, 1)));
      if (s.Board [s.Column, 2] == 0)
        successors.Add (new ActionState (Actions.Row2, new State (s, 2)));
      if (s.Board [s.Column, 3] == 0)
        successors.Add (new ActionState (Actions.Row3, new State (s, 3)));
      if (s.Board [s.Column, 4] == 0)
        successors.Add (new ActionState (Actions.Row4, new State (s, 4)));
      if (s.Board [s.Column, 5] == 0)
        successors.Add (new ActionState (Actions.Row5, new State (s, 5)));
      if (s.Board [s.Column, 6] == 0)
        successors.Add (new ActionState (Actions.Row6, new State (s, 6)));
      if (s.Board [s.Column, 7] == 0)
        successors.Add (new ActionState (Actions.Row7, new State (s, 7)));

      return successors;
    }

    public bool GoalTest (IState state)
    {
      State s = state as State;
      if (s == null)
        throw new ArgumentException ();

      if (s.Column < 8)
        return false;

      return true;
    }

    public double EstimatedCostToGoal (IState state)
    {
      throw new NotImplementedException ();
    }

    public double StepCost (IState from, IAction action, IState to)
    {
      return 1.0;
    }

#endregion
  }
}
